package leetcode.od;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/18 8:18
 * 【编程 | 200分】分糖果 II
 * <p>
 * 题目描述
 * <p>
 * Solo和koko是两兄弟，妈妈给了他们一大袋糖，每块糖上都有自己的重量。现在他们想要将这些糖分成两堆。
 * <p>
 * 分糖的任务当然落到了大哥Solo的身上，然而koko要求必须两个人获得的糖的总重量“相等”（根据Koko的逻辑），要不然就会哭的。
 * <p>
 * 非常不幸的是，koko还非常小，并且他只会先将两个数转成二进制再进行加法，而且总会忘记进位。
 * <p>
 * 如当12（1100）加5（101）时：
 * <p>
 * alt
 * <p>
 * 于是koko得到的计算结果是9（1001）。
 * <p>
 * 此外还有一些例子：
 * <p>
 * 5 + 4 = 1
 * 7 + 9 = 14
 * 50 + 10 = 56
 * 现在Solo非常贪婪，他想要尽可能使自己得到的糖的总重量最大，且不让koko哭。
 * <p>
 * 输入的第一行是一个整数N(2 ≤ N ≤ 15)，表示有袋中多少块糖。
 * 第二行包含N个用空格分开的整数Ci (1 ≤ Ci ≤ 10^6)，表示第 i 块糖的重量。
 * <p>
 * 输出
 * 如果能让koko不哭，输出Solo所能获得的糖的总重量，否则输出“NO”。
 * <p>
 * 样例
 * 输入样例 1
 * 3
 * 3 5 6
 * 输出样例 1
 * 11
 * 提示样例 1
 * 样例1中，三块糖重量为3、5、6，因为5(101)+6(110)=3(11)，所以Solo拿走了重为5和6的糖，koko则得到了重为3的糖。
 * <p>
 * 输入样例 2
 * 5
 * 1 2 3 4 5
 * 输出样例 2
 * 1
 * NO
 */
public class _分糖果II {
    /*思路：   找到所有分为两组的组合，找到满足条件的组合的最大值
    * 只需要第一个组合的size小于等于1/2的整个数组长度即可剪枝
    * 是否满足条件就是切分的两个子数组位异或是否相等
    * */
    @Test
    public void T_0() {
        int[][] nums = {{3, 5, 6}, {1, 2, 3,4,5}};
        int[] ans = {11, -1};
        for (int i = 1; i < nums.length; i++) {
            System.out.println(solution(nums[i]) == ans[i]);
        }
    }

    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    private int solution_review(int[] nums) {
        int res = 1;
        for (int num : nums) {
            res ^= num;
        }
        if(res != 0){
            return -1;
        }

        return 0;
    }
    private int solution(int[] nums) {

        Arrays.sort(nums);
        ArrayList<Integer> nList = new ArrayList<>();
        for (int num : nums) {
            nList.add(num);
        }
        Integer []max = {-1};
        int sum = sum(nums);
        dfs(0, nList,max,sum);
        return max[0];
    }


    private void dfs(int i, ArrayList<Integer> nums, Integer[] max, int sum) {
        if ( i > (nums.size() >> 1)) {
            return;
        }

        //判断是否满足条件
        int s1 = 0;
        for (int j = 0; j <= i; j++) {
            s1 = s1 ^ nums.get(j);
        }
        int s2 = 0;
        for (int j = i+1; j < nums.size(); j++) {
            s2 = s2 ^ nums.get(j);
        }
        if(s1 == s2){
            int sum1 = sum(nums,i);
            max[0] = Math.max(max[0],Math.abs(sum - sum1));
        }

        for (int j = i; j < nums.size(); j++) {
            if (j > i && nums.get(j).equals(nums.get(i))) {
                continue;
            }
            path.add(nums.get(i));
            Collections.swap(nums,i,j);
            dfs(j + 1, nums,max,sum);
            Collections.swap(nums,i,j);
            path.removeLast();
        }
    }
    public int sum(int []nums){
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
    private int sum(ArrayList<Integer> nums, int i) {
        int sum = 0;
        for (int i1 = 0; i1 <= i; i1++) {
            sum += nums.get(i1);
        }

        return sum;
    }
}
